
read _Doc_ =
"
Linked List
"

page _Node[A]:

    init Element % A
    init Before % _Node[A]? = none
    init After % _Node[A]? = none
    
    read Length:
        if After is none:
            return 0
        else:
            return After.Length + 1

###

page _List(A):

    cell _FirstNode % _Node[A] = none
    cell _LastNode % _Node[A] = none

    write AppendToLeft:
        node = _Node(Element = input,
                     After = _FirstNode)
        if _FirstNode is not none:
            _FirstNode.Before = node
        else:
            _LastNode = node

    read _AreFirstAndLastTheSame:
        return ((_FirstNode is none) and (_LastNode is none))
            or ((_FirstNode is not none) and (_LastNode is not none))

    assert _AreFirstAndLastTheSame

    read Length:
        if _FirstNode is none:
            return 0
        else:
            return _FirstNode.Length

###

type List[A] = _List[A]

###

read Empty[A] = _List[A]()
